import collections
from typing import List


# """
# This is FontInfo's API interface.
# You should not implement it, or speculate about its implementation
# """
class FontInfo(object):
    def getWidth(self, fontSize, ch):
        """
        :type fontSize: int
        :type ch: char
        :rtype int
        """
        return 0

    def getHeight(self, fontSize):
        """
        :type fontSize: int
        :rtype int
        """
        return 0


class Solution:
    def maxFont(self, text: str, w: int, h: int, fonts: List[int], fontInfo: 'FontInfo') -> int:
        count = collections.Counter(text)

        left, right = -1, len(fonts) - 1
        while left < right:
            mid = (left + right) // 2 + 1

            if fontInfo.getHeight(fonts[mid]) > h:
                right = mid - 1
                continue

            length = 0
            for ch, v in count.items():
                length += fontInfo.getWidth(fonts[mid], ch) * v

            if length <= w:
                left = mid
            else:
                right = mid - 1

        return fonts[left] if left >= 0 else -1


if __name__ == "__main__":
    pass
